package qjc.a_哈希;

import java.util.HashSet;

public class c_最长连续序列 {
    /**
     * 定义一个哈希Set，判断该值-1是否存在，判断是否是连续的数组起点，
     * 如果是则continue，不是则判断+1，存在则继续判断下一个值，
     * 如果长度大于数组长度的一半则提前退出，否则返回最大长度
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        int max = 0;
        int size = set.size();
        for(int num : set){
            if(set.contains(num-1)){
                continue;
            }
            int y = num + 1;
            while (set.contains(y)){
                y++;
            }
            max = Math.max(max,y-num);
            if(max * 2 >= size){
                break;
            }
        }
        return max;
    }
}
